//https://leetcode.cn/problems/tree-of-coprimes/?envType=daily-question&envId=2024-04-11


class Solution {
public:
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        vector<int> p[51];
        for (int i = 1; i < 51; i++)
        for (int j = 1; j < 51; j++) {
            if (gcd(i,j) == 1)
            p[i].emplace_back(j);
        }
        int n = nums.size();
        vector<int> g[n];
        for (const auto &e: edges) {
            int u = e[0], v = e[1];
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        vector<int> ans(n, -1);
        vector<pair<int,int>> stk[51];
        function<void(int,int,int)> dfs = [&] (int cur, int pre, int lev) {
            int cv = nums[cur];
            int maxl = -1, tgt = -1;
            for (auto &i: p[cv]){
                if (stk[i].size()) {
                    auto &[tt, tl] = stk[i].back();
                    if (tl > maxl) {
                        maxl = tl;
                        tgt = tt;
                    }
                }
            }
            ans[cur] = tgt;

            stk[nums[cur]].emplace_back(cur,lev);
            for (const auto &nxt: g[cur]) {
                if (nxt == pre) continue;
                dfs(nxt, cur, lev+1);
            }
            stk[nums[cur]].pop_back();
        };
        dfs(0, -1, 0);
        return ans;
    }
};